package 前缀系列;

import java.util.Arrays;
/**
 * 经典 
 * 
 * 
 * 这种 纯暴力 写法 直接  已经不是  时间 超限了 而是 内存 都 已经 超限了 
 * 这个 空字符串 还是 必须 要 加 的 要不然  怎么 排序 就无法  去 排序  因为 nums[0] == null;
 * 字符串的  问题 还是 要  十分 注意 这里 会有 很多的 问题 
 * @author I adore you
 *
 */
public class leetcode440字典序的第k小数字 {
	public static void main(String []args) {
		System.out.println(solution(13,2));
		String str [] =new String[] {"1","2","10","3","11","23"};
		Arrays.sort(str);
		System.out.println(Arrays.toString(str));
		System.out.println(1+""+2);
	}
	public static String solution(int n,int k) {
		String nums[] = new String[n+1];
//		      这个 空字符串 还是 必须 要 加 的 要不然  怎么 排序 就无法  去 排序  因为 nums[0] == null;
		nums[0] = "";
		for(int i = 1;i <= n;i++) {
			nums[i] = i+"";
		}
		Arrays.sort(nums);
//		for(int i=1;i<=k) {
//			
//		}
		return nums[k];
	}
}
/**
 * 先不写 着   这个 东西   多回顾 这道题 的  最优解法  
 * 这是 真的 强 
 * 看明白 整个 过程 之后 这是真的 牛逼 
 * @author I adore you
 *
 */
class Solution {
    public int findKthNumber(int n, int k) {
        long cur = 1; // 当前遍历到的数字，从1（根）出发
        k = k - 1; // 从1出发开始往后按字典序从小到大的顺序走k-1步到达的就是 字典序的第K小数字

        while(k > 0){
            int nodes = getNodes(n, cur);
            if(k >= nodes){ // 向右侧节点走：字典序上升nodes位
                k =  k - nodes;
                cur++;  // 当前数字 cur = cur + 1
            }else{ // 向下往最左孩子节点走:字典序上升1位
                k = k - 1; 
                cur *= 10;  // 当前数字 cur = cur * 10
            }
        }
        return (int)cur; // 最后cur停在的数字就是字典序的第K小数字
    }

    // 计算以cur为根的子树节点数目，所有节点的值必须 <= n
    private int getNodes(int n, long cur){
        long next = cur + 1; // 当前节点右侧右边节点的值
        long totalNodes = 0; // 记录子树中的全部节点数目
        while(cur <= n){
/**
 * 下面的 这一行 代码  是  非常 核心的   代码  它的 作用 能 卡 住 两个 边界 n 过大时
 * n 过小 时   都取 最小值 
 */
            totalNodes += Math.min(n - cur + 1, next - cur);
            next *= 10;
            cur *= 10;
        }
        return (int)totalNodes;
    }
}
